package com.captain.leetcode.二叉树;

import com.captain.leetcode.TreeNode;

import java.util.LinkedList;

/**
 * Des:
 * 给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。
 * <p>
 * 每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * <p>
 * 1
 * /   \
 * 3     2
 * / \     \
 * 5   3     9
 * <p>
 * 输出: 4
 * 解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
 * 示例 2:
 * <p>
 * 输入:
 * <p>
 * 1
 * /
 * 3
 * / \
 * 5   3
 * <p>
 * 输出: 2
 * 解释: 最大值出现在树的第 3 层，宽度为 2 (5,3)。
 * 示例 3:
 * <p>
 * 输入:
 * <p>
 * 1
 * / \
 * 3   2
 * /
 * 5
 * <p>
 * 输出: 2
 * 解释: 最大值出现在树的第 2 层，宽度为 2 (3,2)。
 * 示例 4:
 * <p>
 * 输入:
 * <p>
 * 1
 * / \
 * 3   2
 * /     \
 * 5       9
 * /         \
 * 6           7
 * 输出: 8
 * 解释: 最大值出现在树的第 4 层，宽度为 8 (6,null,null,null,null,null,null,7)。
 * <p>
 * 补充 : 最左和最右的差 + 1  = 最大的宽度
 * @author XL
 * @Date 2021/7/26 12:41
 */
public class 二叉树最大宽度662 {

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        //存储记录节点信息
        LinkedList<TreeNode> queue = new LinkedList<>();
        root.val = 1;
        queue.offer(root);
        int maxValue;
        maxValue = 0;
        while (!queue.isEmpty()) {
            int n = queue.size();
            int left = queue.peekFirst().val;
            int right = queue.peekLast().val;
            maxValue = Math.max(maxValue, right - left + 1);
            for (int i = 0; i < n; i++) {
                //广度优先
                TreeNode node = queue.poll();
                if (node != null) {
                    int position = node.val;
                    if (node.left != null) {
                        node.left.val = position * 2;
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        node.right.val = position * 2 + 1;
                        queue.offer(node.right);
                    }
                }
            }
        }
        return maxValue;
    }
}
